/**
 * Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.
 */
package com.xinpan.exercise;


//do again
public class FirstMissingPositive {
    public int firstMissingPositive(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        for(int i = 0; i < A.length; )
        {
            if(A[i] != i+1 && A[i] > 0 && A[i] <= A.length && A[A[i]-1] != A[i])
            {
                int t1 =  A[A[i]-1];
                int t2 = A[i];
                A[i] = t1;
                A[A[i]-1] = t2;
            }
            else 
            	i++;
        }
        for(int i = 0; i < A.length; i++)
            if(A[i] != i+1)
                return i+1;
        
        return A.length+1;
    }
    
    public static void main(String[] args)
    {
    	int[] A = {3, 4, -1, 1};
    	FirstMissingPositive fmp = new FirstMissingPositive();
    	fmp.firstMissingPositive(A);
    }
}
